import java.util.*;

public class Solution347 {
    /**
     * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
     * <p>
     * 示例 1:
     * <p>
     * 输入: nums = [1,1,1,2,2,3], k = 2
     * 输出: [1,2]
     */
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<List<Integer>> lists = new ArrayList<>(nums.length);
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
            if (lists.size() < map.get(num)) {
                lists.add(new ArrayList<>());
            }
            lists.get(map.get(num) -1).add(num);
        }
        for (int i = lists.size() - 1; i >= 0; i--) {
            if (lists.get(i).size() >= k) {
                return lists.get(i);
            }
        }
        return null;
    }
}
